简单构造题。
题意:给定 个数,是否能排成一圈,使相邻两个数差 。
根据题意,为了使相邻两个数差 ,圆圈中 和 的次数必定相等才能组成闭环,因此 必须是偶数,对于奇数可以直接输出无解(代码注释 {1})。
然后同样根据相邻两个数差 的性质,我们将原数列排序,枚举相邻两个下标的数,如果差大于 也输出无解(代码注释 {2})。
之后找到数列最小值,把每个数减去最小值再加 ,即可得到一串与原数列等效的、最小值为 的数列,经过前面两个特判,可以保证最大值不超过 。然后从最小值开始,可以 时选择 ,否则看看是否可以 ,若不可以就跳出循环。
由于闭环性质,要形成环则最后一个数必定是 ,如果不是 则不能成环,输出无解(代码注释 {3})。
否则将整个桶扫一遍,如果有地方不为 则代表成环失败,实处物价(代码注释 {4})。
否则即代表我们构造出了一个符合题意的环,输出有解即可。
这样就水过了一道 CF *2000 的构造题(
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5, inf = 1e9;
int n, a[N], buc[N], mi = inf;
int main() {
scanf("%d", &n);
if(n & 1) return puts("NO"), 0; // {1}
rep(i, 1, n) scanf("%d", &a[i]), mi = min(mi, a[i]);
sort(a+1, a+1+n);
rep(i, 2, n) if(a[i] - a[i-1] > 1) return puts("NO"), 0; // {2}
rep(i, 1, n) ++buc[a[i]-mi+1];
int u = 1; --buc[1];
loop {
if(buc[u+1]) --buc[++u];
else if(buc[u-1]) --buc[--u];
else break;
}
if(u != 2) return puts("NO"), 0; // {3}
rep(i, 0, N-1) if(buc[i]) return puts("NO"), 0; // {4}
return puts("YES"), 0;
}